home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / index / utils.c.z / utils.c
C/C++ Source or Header  |  1997-09-09  |  8KB  |  377 lines
  1. #include "glimpse.h"
  2. /* n is guaranteed to be < MaxNum4bPartition */
  3.  
  4. int
  5. encode4b(n)
  6.     int    n;
  7. {
  8.     if (n=='\0') return MaxNum4bPartition;
  9.     if (n=='\n') return MaxNum4bPartition+1;
  10.     return n;
  11. }
  12.  
  13. int
  14. decode4b(n)
  15.     int n;
  16. {
  17.     if (n==MaxNum4bPartition) return '\0';
  18.     if (n==MaxNum4bPartition+1) return '\n';
  19.     return n;
  20. }
  21.  
  22. /* n is guaranteed to be < MaxNum8bPartition */
  23.  
  24. int
  25. encode8b(n)
  26.     int n;
  27. {
  28.     if (n=='\0') return MaxNum8bPartition;
  29.     if (n=='\n') return MaxNum8bPartition+1;
  30.     return n;
  31. }
  32.  
  33. int
  34. decode8b(n)
  35.     int n;
  36. {
  37.     if (n==MaxNum8bPartition) return '\0';
  38.     if (n==MaxNum8bPartition+1) return '\n';
  39.     return n;
  40. }
  41.  
  42. /* n is guaranteed to be < MaxNum12bPartition */
  43.  
  44. int
  45. encode12b(n)
  46.     int n;
  47. {
  48.     unsigned char msb, lsb;
  49.  
  50.     msb = (n / MaxNum8bPartition);
  51.     lsb = (n % MaxNum8bPartition);
  52.     msb = encode4b(msb);
  53.     lsb = encode8b(lsb);
  54.     return (msb<<8)|lsb;
  55. }
  56.  
  57. int
  58. decode12b(n)
  59.     int n;
  60. {
  61.     unsigned char msb, lsb;
  62.  
  63.     msb = ((n&0x00000f00) >> 8);
  64.     lsb = (n&0x000000ff);
  65.     msb = decode4b(msb);
  66.     lsb = decode8b(lsb);
  67.     return (msb * MaxNum8bPartition) + lsb;
  68. }
  69.  
  70. /* n is guaranteed to be < MaxNum16bPartition */
  71.  
  72. int
  73. encode16b(n)
  74.     int n;
  75. {
  76.     unsigned char msb, lsb;
  77.  
  78.     msb = (n / MaxNum8bPartition);
  79.     lsb = (n % MaxNum8bPartition);
  80.     msb = encode8b(msb);
  81.     lsb = encode8b(lsb);
  82.     return (msb<<8)|lsb;
  83. }
  84.  
  85. int
  86. decode16b(n)
  87.     int n;
  88. {
  89.     unsigned char msb, lsb;
  90.  
  91.     msb = ((n&0x0000ff00) >> 8);
  92.     lsb = (n&0x000000ff);
  93.     msb = decode8b(msb);
  94.     lsb = decode8b(lsb);
  95.     return (msb * MaxNum8bPartition) + lsb;
  96. }
  97.  
  98. /* n is guaranteed to be < MaxNum24bPartition */
  99.  
  100. int
  101. encode24b(n)
  102.     int n;
  103. {
  104.     unsigned short msb, lsb;
  105.  
  106.     msb = (n / MaxNum16bPartition);
  107.     lsb = (n % MaxNum16bPartition);
  108.     msb = encode8b(msb);
  109.     lsb = encode16b(lsb);
  110.     return (msb<<16)|lsb;
  111. }
  112.  
  113. int
  114. decode24b(n)
  115.     int n;
  116. {
  117.     unsigned short msb, lsb;
  118.  
  119.     msb = ((n&0x00ff0000) >> 16);
  120.     lsb = (n&0x0000ffff);
  121.     msb = decode8b(msb);
  122.     lsb = decode16b(lsb);
  123.     return (msb * MaxNum16bPartition) + lsb;
  124. }
  125.  
  126. /* n is guaranteed to be < MaxNum32bPartition */
  127.  
  128. int
  129. encode32b(n)
  130.     int n;
  131. {
  132.     unsigned short msb, lsb;
  133.  
  134.     msb = (n / MaxNum16bPartition);
  135.     lsb = (n % MaxNum16bPartition);
  136.     msb = encode16b(msb);
  137.     lsb = encode16b(lsb);
  138.     return (msb<<16)|lsb;
  139. }
  140.  
  141. int
  142. decode32b(n)
  143.     int n;
  144. {
  145.     unsigned short msb, lsb;
  146.  
  147.     msb = ((n&0xffff0000) >> 16);
  148.     lsb = (n&0x0000ffff);
  149.     msb = decode16b(msb);
  150.     lsb = decode16b(lsb);
  151.     return (msb * MaxNum16bPartition) + lsb;
  152. }
  153.  
  154. /*
  155.  * converts file-names with *,. and ? and converts it to # \. and ? ALL OTHER agrep-special characters are masked off.
  156.  * if the filename NOT a regular expression involving ? or *, it leaves the name untouched and returns the string
  157.  * length of the file name (so that we can avoid memagrep calls): otherwise, it returns the -ve strlength of the name
  158.  * after performing the above conversion: hence we never need to call agrep if the length is +ve.
  159.  */
  160. int
  161. convert2agrepregexp(buf, len)
  162.     char    *buf;
  163.     int    len;
  164. {
  165.     char    tbuf[MAX_PAT];
  166.     int    i=0, j=0;
  167.  
  168.     /* Ignore '*' at the beginning and '*' at the end */
  169.     if (len < 1) return 0;
  170.     if ( ((len == 1) && (buf[len-1] == '*')) || ((len >= 2) && (buf[len-1] == '*') && (buf[len-1] != '\\')) ) {
  171.         buf[len-1] = '\0';
  172.         len--;
  173.     }
  174.     if (buf[0] == '*') {
  175.         for (i=0; i<len; i++)
  176.             buf[i] = buf[i+1];
  177.         len--;
  178.     }
  179.     if (len < 1) {
  180.         buf[0] = '.';
  181.         buf[1] = '*';
  182.         buf[2] = '\0';
  183.         return -2;
  184.     }
  185.  
  186.     for (i=0; i<len; i++)
  187.         if (buf[i] == '\\') i++;
  188.         else if ((buf[i] == '?') || (buf[i] == '*')
  189.             || (buf[i] == '$') || (buf[i] == '^')) break;
  190.     if (i >= len) return len;
  191.  
  192.     i = j = 0;
  193.     while ((i<len) && (j<MAX_PAT) && (buf[i] != '\0')) {
  194.         /* Consider all special characters interpreted by agrep */
  195.         if (buf[i] == '\\') {
  196.             /* copy two things without interpreting them */
  197.             tbuf[j++] = buf[i++];
  198.             tbuf[j++] = buf[i++];
  199.         }
  200.         else if ((buf[i] == '-') || (buf[i] == ',') || (buf[i] == ';')||
  201.              (buf[i] == '.') || (buf[i] == '#') || (buf[i] == '|')||
  202.              (buf[i] == '[') || (buf[i] == ']') || (buf[i] == '(')||
  203.              (buf[i] == ')') || (buf[i] == '>') || (buf[i] == '<')||
  204.              /* (buf[i] == '^') || (buf[i] == '$') || */
  205.              (buf[i] == '+')||
  206.              (buf[i] == '{') || (buf[i] == '}') || (buf[i] == '~')){
  207.             tbuf[j++] = '\\';
  208.             tbuf[j++] = buf[i];
  209.             i++;
  210.         }
  211.         /* Interpret ONLY ? and * in file-names */
  212.         else if (buf[i] == '?') {
  213.             tbuf[j++] = '.';
  214.             i++;
  215.         }
  216.         else if (buf[i] == '*') {
  217.             tbuf[j++] = '.';
  218.             tbuf[j++] = '*';
  219.             i++;
  220.         }
  221.         else tbuf[j++] = buf[i++];
  222.     }
  223.  
  224.     if (j >= MAX_PAT) {
  225.         tbuf[j-1] = '\0';
  226.         fprintf(stderr, "glimpseindex: pattern '%s' too long\n", buf);
  227.         j--;
  228.     }
  229.     else {
  230.         tbuf[j] = '\0';
  231.     }
  232.  
  233.     strcpy(buf, tbuf);
  234. #if    0
  235.     printf("%s=%d\n", buf, j);
  236. #endif    /*0*/
  237.     return -j;    /* strlen-compatible, -ve to indicate memagrep must be called */
  238. }
  239.  
  240. /* -----------------------------------------------------------------
  241. input: a word (a string of ascii character terminated by NULL)
  242. output: a hash_value of the input word.
  243. hash function: if the word has length <= 4
  244.         the hash value is just a concatenation of the last four bits
  245.         of the characters.
  246.         if the word has length > 4, then after the above operation,
  247.         the hash value is updated by adding each remaining character.
  248.         (and AND with the 16-bits mask).
  249. bug-fixes in all hashing functions: Chris Dalton
  250. ---------------------------------------------------------------- */
  251. int
  252. hash64k(word, len)
  253. char *word;
  254. int len;
  255. {
  256.     unsigned int hash_value=0;
  257.     unsigned int mask_4=017;
  258.     unsigned int mask_16=0177777;
  259.     int i;
  260.  
  261.     if(len<=4) {
  262.     for(i=0; i<len; i++) {
  263.                hash_value = (hash_value << 4) | (word[i]&mask_4);
  264.         /* hash_value = hash_value  & mask_16; */ 
  265.     }
  266.     }
  267.     else {
  268.     for(i=0; i<4; i++) {
  269.                hash_value = (hash_value << 4) | (word[i]&mask_4);
  270.         /* hash_value = hash_value & mask_16;  */
  271.     }
  272.     for(i=4; i<len; i++) 
  273.         hash_value = mask_16 & (hash_value + word[i]);
  274.     }
  275.     return(hash_value & mask_16);
  276. }
  277.  
  278. /*
  279.  * Explicitly used with -B option
  280.  */
  281. int
  282. hash256k(word, len)
  283. char *word;
  284. int len;
  285. {
  286.     unsigned int hash_value=0;
  287.     unsigned int mask_4=017;
  288.     unsigned int mask_5=037;
  289.     unsigned int mask_18=0x3ffff;
  290.     int i;
  291.  
  292.     if(len<=4) {
  293.     for(i=0; i<len; i++) {
  294.                if ((i % 2) == 0) hash_value = (hash_value << 5) | (word[i]&mask_5);
  295.         else hash_value = (hash_value << 4) | (word[i]&mask_4);
  296.         /* hash_value = hash_value  & mask_18; */ 
  297.     }
  298.     }
  299.     else {
  300.     for(i=0; i<4; i++) {
  301.                if ((i % 2) == 0) hash_value = (hash_value << 5) | (word[i]&mask_5);
  302.                else hash_value = (hash_value << 4) | (word[i]&mask_4);
  303.         /* hash_value = hash_value & mask_18;  */
  304.     }
  305.     for(i=4; i<len; i++) 
  306.         hash_value = mask_18 & (hash_value + word[i]);
  307.     }
  308.     return(hash_value & mask_18);
  309. }
  310.  
  311. /*
  312.  * Explicitly used for veryfastsearch without WORD_SORTED
  313.  * Using > 5 bits is waste since there are only 26 lower case letters
  314.  */
  315. int
  316. hash32k(word, len)
  317.     char     *word;
  318.     int    len;
  319. {
  320.     unsigned int hash_value=0;
  321.     unsigned int mask_5=037;
  322.     unsigned int mask_15=077777;
  323.     int i;
  324.  
  325.     if(len<=3) {
  326.     for(i=0; i<len; i++) {
  327.                hash_value = (hash_value << 5) | (word[i]&mask_5);
  328.     }
  329.     }
  330.     else {
  331.     for(i=0; i<3; i++) {
  332.                hash_value = (hash_value << 5) | (word[i]&mask_5);
  333.     }
  334.     for(i=3; i<len; i++) 
  335.         hash_value = mask_15 & (hash_value + word[i]);
  336.     }
  337.     return(hash_value & mask_15);
  338. }
  339.  
  340. /* This function is utterly disgraceful */
  341. int
  342. hash16k(word, len)
  343.     char    *word;
  344.     int    len;
  345. {
  346.     return hash32k(word, len) & 0x3fff;
  347. }
  348.  
  349. /*
  350.  * Explicitly used for -f and -a options: has low collisions (<=2) for filenames
  351.  */
  352. int
  353. hash4k(word, len)
  354.     char     *word;
  355.     int    len;
  356. {
  357.     unsigned int hash_value=0;
  358.     unsigned int mask_3=07;
  359.     unsigned int mask_12=07777;
  360.     int i;
  361.  
  362.     if(len<=4) {
  363.     for(i=0; i<len; i++) {
  364.                hash_value = (hash_value << 3) | (word[i]&mask_3);
  365.     }
  366.     }
  367.     else {
  368.     for(i=0; i<4; i++) {
  369.                hash_value = (hash_value << 3) | (word[i]&mask_3);
  370.     }
  371.     for(i=4; i<len; i++) 
  372.         hash_value = mask_12 & (hash_value + word[i]);
  373.     }
  374.     return(hash_value & mask_12);
  375. }
  376.  
  377.